package club.babyf.nativeai.demo.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * _35_FindMaxLength.
 *
 * @author zhanglei.
 * @date 2025/9/21 21:20.
 * @description 连续数组.
 * 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
 * 示例 1：
 * <p>
 * 输入：nums = [0,1]
 * 输出：2
 * 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
 * 示例 2：
 * <p>
 * 输入：nums = [0,1,0]
 * 输出：2
 * 说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
 * 示例 3：
 * <p>
 * 输入：nums = [0,1,1,1,1,1,0,0,0]
 * 输出：6
 * 解释：[1,1,1,0,0,0] 是具有相同数量 0 和 1 的最长连续子数组。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 105
 * nums[i] 不是 0 就是 1
 */
public class _35_FindMaxLength {

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int prefixSum = 0;
        int maxLength = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                prefixSum -= 1;
            } else {
                prefixSum += 1;
            }

            if (map.containsKey(prefixSum)) {
                int prevIndex = map.get(prefixSum);
                maxLength = Math.max(maxLength, i - prevIndex);
            } else {
                map.put(prefixSum, i);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        _35_FindMaxLength findMaxLength = new _35_FindMaxLength();
        int[] nums = {0, 1, 1, 1, 1, 1, 0, 0, 0};
        int maxLength = findMaxLength.findMaxLength(nums);
        System.out.println(maxLength);
    }

}
